11161. Fruit Feast

Bessie has broken into Farmer John’s house again! She has discovered a pile of lemons and a pile of oranges in the kitchen (effectively an unlimited number of each), and she is determined to eat as much as possible.

Bessie has a maximum fullness of t. Eating an orange increases her fullness by a, and eating a lemon increases her fullness by b. Additionally, if she wants, Bessie can drink water at most one time, which will instantly decrease her fullness by half (and will round down).

Help Bessie determine the maximum fullness she can achieve!

Input. One line has three integers t (1 ≤ t ≤ 5 ⋅ 10⁶), a and b (1 ≤ a, b ≤ t).

Output. Print a single integer, representing the maximum fullness Bessie can achieve.

Sample input	Sample output
8 5 6	8

SOLUTION

knapsack

Algorithm analysis

There is a knapsack with a capacity of t. Two items are available with values a and b. Each item in the knapsack can be placed an arbitrary number of times. We solve the knapsack problem for these two items.

Let dp[i] = 1, if Bessie can achieve fullness equal to i. Now Bessie drinks the water. For each value of i where dp[i] = 1, we set dp[i / 2] = 1.

Now again solve the knapsack problem for two items. Determine the fullness that Bessie can achieve after drinking the water.

Example

Consider the given example. First we solve the knapsack problem for oranges and lemons.

Bessie drinks water.

Again we solve the knapsack problem for oranges and lemons.

Bessie’s maximum fullness is 8.

Algorithm realization

Declare an array dp, where dp[i] = 1, if Bessie can achieve fullness equal to i.

#define MAX 5000001

int dp[MAX];

Read the input data.

scanf("%d %d %d", &t, &a, &b);

Initialize the knapsack: fullness 0 can be achieved if nothing is eaten.

dp[0] = 1;

Put oranges in the knapsack.

for (i = a; i <= t; i++)

if (dp[i - a] == 1) dp[i] = 1;

Put lemons in the knapsack.

for (i = b; i <= t; i++)

if (dp[i - b] == 1) dp[i] = 1;

Bessie drinks water. If fullness i is achieved, then fullness i / 2 can also be achieved.

for (i = 1; i <= t; i++)

if (dp[i] == 1) dp[i / 2] = 1;

Solve the knapsack problem again for oranges and lemons.

for (i = a; i <= t; i++)

if (dp[i - a] == 1) dp[i] = 1;

for (i = b; i <= t; i++)

if (dp[i - b] == 1) dp[i] = 1;

Find and print the maximum fullness that Bessie can achieve.

for (i = t; i > 0; i--)

if (dp[i] == 1) break;

printf("%d\n", i);

Python realization

Read the input data.

t, a, b = map(int, input().split())

Declare a list dp, where dp[i] = 1, if Bessie can achieve fullness equal to i.

dp = [0] * (t + 1)

Initialize the knapsack: fullness 0 can be achieved if nothing is eaten.

dp[0] = 1

Put oranges in the knapsack.

for i in range(a, t + 1):

if dp[i - a] == 1: dp[i] = 1

Put lemons in the knapsack.

for i in range(b, t + 1):

if dp[i - b] == 1: dp[i] = 1

Bessie drinks water. If fullness i is achieved, then fullness i / 2 can also be achieved.

for i in range(1, t + 1):

if dp[i] == 1: dp[i // 2] = 1

Solve the knapsack problem again for oranges and lemons.

for i in range(a, t + 1):

if dp[i - a] == 1: dp[i] = 1

for i in range(b, t + 1):

if dp[i - b] == 1: dp[i] = 1

Find and print the maximum fullness that Bessie can achieve.

for i in range(t, 0, -1):

if dp[i] == 1: break

print(i)